package leetcode101_xqzhao

// TODO 不同的二叉搜索树 【-】 动态规划

func numTrees(n int) int {
	// 定义状态数组
	dp := make([]int, n+2) // 其实 n+1 就够, n+2 则不用单独处理 n==1 的情况

	// 定义初始值  // dp[0]的作用: dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]
	dp[0] = 1
	dp[1] = 1
	dp[2] = 2

	// 状态转移
	for i := 3; i <= n; i++ {
		for j := 1; j <= i; j++ {
			dp[i] += dp[j-1] * dp[i-j]
		}
	}

	return dp[n]
}
